package com.lm.leetcode.arr;

import java.util.*;

/**
 * @Auther: Min.Liu
 * @Description:
 * @Date: Created in 8:31 2025/5/8
 */
public class TwoDimArrayDemo {
    public static void main(String[] args) {
        TwoDimArrayDemo demo = new TwoDimArrayDemo();
//        int[][] arr= {{6,3},{7,2},{4,8}};
//        int[][] newarr = demo.merge(arr);
//        int[][] arr= {{ 5, 1, 9,11},{2, 4, 8,10},{13, 3, 6, 7},{15,14,12,16}};
//        demo.rotate(arr);
        //int[][] arr = {{5, 1, 0, 11, 19}, {2, 4, 8, 0, 11}, {13, 0, 3, 6, 7}, {15, 14, 7, 12, 16}};
        //demo.setZeroes(arr);
        //demo.setZeroesOther(arr);
        //demo.setZeroesOther2(arr);
        int[][] arr = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}};
        for (int[] ints : arr) {
            System.out.print("[");
            for (int anInt : ints) {
                System.out.print(anInt + ",");
            }
            System.out.println("]");
        }
        int[] newlist = demo.findDiagonalOrder(arr);
        System.out.print("[");
        for (int anInt : newlist) {
            System.out.print(anInt + ",");
        }
        System.out.println("]");
    }

    /*
        以数组 intervals 表示若干个区间的集合，
        其中单个区间为 intervals[i] = [starti, endi] 。
        请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间
     */
    public int[][] merge(int[][] intervals) {
        for (int[] interval : intervals) {
            Arrays.sort(interval);
        }
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        int[] temp = intervals[0];
        ArrayList<int[]> arrayList = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            if (temp[1] >= intervals[i][0]) {
                temp[1] = Math.max(temp[1], intervals[i][1]);
            } else {
                arrayList.add(temp);
                temp = intervals[i];
            }
        }
        arrayList.add(temp);
        return arrayList.toArray(new int[arrayList.size()][2]);
    }

    /*
       给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
       不占用额外内存空间能否做到？
       分析：
                                 len=4         x,y -> 1,0  j i
        x y int[y][x]         x,y -> len-1-y,x              len-1-y,x -> 3,1
      0,0 1,0 2,0 3,0         x,y -> len-1-y,x        len-1-x,len-1-y -> 2,3
      0,1 1,1 2,1 3,1         x,y -> len-1-y,x              y,len-1-x -> 0,2
      0,2 1,2 2,2 3,2
      0,3 1,3 2,3 3,3
     */
    public void rotate(int[][] matrix) {
        int len = matrix.length;
        for (int i = 0; i < matrix.length - 1; i++) {
            //注意调换只用调换矩阵的1/4 就完成了  不做限制 就换了四次  就还原了
            for (int j = i; j < matrix.length - 1 - i; j++) {
                exchange(matrix, j, i, len - 1 - i, j);
                exchange(matrix, j, i, len - 1 - j, len - 1 - i);
                exchange(matrix, j, i, i, len - 1 - j);
            }
        }
    }

    public void exchange(int[][] matrix, int prex, int prey, int lastx, int lasty) {
        /** A和B交换思路
         * A = A+B;
         * B = A-B;  -> B = A
         * A = A-B;  -> A = B
         */
        matrix[prey][prex] = matrix[prey][prex] + matrix[lasty][lastx];
        matrix[lasty][lastx] = matrix[prey][prex] - matrix[lasty][lastx];
        matrix[prey][prex] = matrix[prey][prex] - matrix[lasty][lastx];
    }


    /*
        编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
     */
    public void setZeroes1(int[][] matrix) {
//        int[] hang = new int[matrix.length];
//        int[] lie = new int[matrix[0].length];
        Set<Integer> hang = new HashSet();
        Set<Integer> lie = new HashSet();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    hang.add(i);
                    lie.add(j);
                }
            }
        }

        for (Integer integer : hang) {
            System.out.println(integer);
            //当前行属于完全删除行 全行清零
            for (int i = 0; i < matrix[integer].length; i++) {
                matrix[integer][i] = 0;
            }
        }
        System.out.println("===");
        for (Integer integer : lie) {
            System.out.println(integer);
            for (int i = 0; i < matrix.length; i++) {
                //当前行不属于完全删除行
                if (!hang.contains(i)) {
                    //一个个清零
                    matrix[i][integer] = 0;
                }
            }
        }
    }

    public void setZeroesOther2(int[][] matrix) {
        Vector<Integer> lie = new Vector<>();
        int r = -1;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    r = i;
                    lie.add(j);
                }
            }
            if (r == i) {
                for (int j = 0; j < matrix[i].length; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (Integer integer : lie) {
            for (int i = 0; i < matrix.length; i++) {
                //一个个清零
                matrix[i][integer] = 0;
            }
        }
    }

    public void setZeroesOther(int[][] matrix) {
        int[] lie = new int[matrix[0].length];
        int r = -1;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    r = i;
                    lie[j] = 1;
                }
            }
            if (r == i) {
                for (int j = 0; j < matrix[i].length; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < lie.length; j++) {
                //一个个清零
                if (lie[j] == 1) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    /*
      对角线遍历 给定数组mat
       1  2  3  4  5
       6  7  8  9  10
       11 12 13 14 15
       16 17 18 19 20
       输出 1,2,5,9,6,3,4,7,10,13,14,11,8,12,15,16
       小数组个数为M 大数组个数为N
       从零开始输出 M+N-1轮 第i轮 输出元素 mat[x][y] 其中x+y=i

     */
    public int[] findDiagonalOrder(int[][] mat) {
        int M = mat[0].length;
        int N = mat.length;
        //创建一个list[]
        //List[] lists = new ArrayList[M + N - 1];
        int[] arr = new int[M * N];
        int index = 0;
        int k = 0, l = 0;
        for (int i = 0; i < M + N - 1; i++) {
            if (i % 2 == 0) { //自下而上
                for (int j = k; j >= i - l; j--) {
                    arr[index] = mat[j][i-j];
                    index++;
                }
            } else {
                for (int j = l; j >= i - k; j--) {
                    arr[index] = mat[i - j][j];
                    index++;
                }
            }
            k = k >= N-1 ? N-1 : k + 1;
            l = l >= M-1 ? M-1 : l + 1;
        }
        return arr;
    }

    public int[] findDiagonalOrder2(int[][] mat) {
        if (mat == null || mat.length == 0 || mat[0].length == 0) { //空矩阵判定
            return new int[0];
        }
        int m = mat.length; //行
        int n = mat[0].length; //列
        int[] list = new int[m * n]; //存放元素的新数组
        int count = 0; //计数
        int i = 0;
        int j = 0;
        boolean direct = true; //方向值（向上为true,向下为false）
        while (count < (m * n)) {
            if (direct) {
                //向上
                while (i >= 0 && j < n) { //到达边界则跳出循环
                    list[count] = mat[i][j]; //将遍历到的元素放入新数组
                    i--; //纵向减少
                    j++; //横向增加
                    count++;
                }
                if (j == n) { //到达边界后进行两种情况判定（上边界还是右边界）
                    j--;
                    i = i + 2;
                } else { //右边界
                    i++;
                }
            } else {
                //向下
                while (i < m && j >= 0) {
                    list[count] = mat[i][j];
                    i++; //纵向增加
                    j--; //横向减少
                    count++;
                }
                if (i == m) { //同上进行判定（下边界还是左边界）
                    i = i - 1;
                    j = j + 2;
                } else {
                    j++;
                }
            }
            direct = !direct; //到达边界后调整方向
        }
        return list;
    }


}
